package lanqiao._01基础练习;

import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 问题描述
 * 给定n个十六进制正整数，输出它们对应的八进制数。
 *
 * 输入格式
 * 　　输入的第一行为一个正整数n （1<=n<=10）。
 * 　　接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。
 *
 * 输出格式
 * 　　输出n行，每行为输入对应的八进制正整数。
 *
 * 【注意】
 * 　　输入的十六进制数不会有前导0，比如012A。
 * 　　输出的八进制数也不能有前导0。
 * 样例输入
 * 　　2
 * 　　39
 * 　　123ABC
 *
 * 样例输出
 * 　　71
 * 　　4435274
 * @since 2022 - 10 - 26 - 23:23
 */
public class _03十六进制转八进制 {
    public static void main(String[] args) {
        for(int i = 0; i < 16; i++){
            System.out.println(getFourBitBinaryStr(i));
        }
    }
    public static String getFourBitBinaryStr(int num){
        String str = Integer.toString(num, 2);
        int len = str.length();
        if(len == 0){
            return "0000";
        }else if(len == 1){
            return "000" + str;
        }else if(len == 2){
            return "00" + str;
        }else if(len == 3){
            return "0" + str;
        }
        return str;
    }
}
class Main{
    //16 -> 8
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        String num;
        while(n > 0){
            num = sc.nextLine();
            System.out.println(get1(num));
            n--;
        }
    }
    //十进制为中介 数据太大会溢出
    public static String get(String num){
        long val = 0;
        int len = num.length();
        //16 -> 10
        for(int i = len - 1; i >= 0; i--){
            if(num.charAt(i) <= '9'){
                if(len - i - 1 == 0)
                    val += (num.charAt(i) - '0');
                else
                    val += (num.charAt(i) - '0') * Math.pow(16, len - i - 1);
            }else{
                if(len - i - 1 == 0)
                    val += (num.charAt(i) - 'A' + 10);
                else
                    val += (num.charAt(i) - 'A' + 10) * Math.pow(16, len - i - 1);
            }
        }
        //10 -> 8
        StringBuilder builder = new StringBuilder();
        while(val != 0){
            builder.insert(0, val % 8);
            val /= 8;
        }
        return builder.toString();
    }
    //二进制位中介
    public static String get1(String str){
        StringBuilder s2 = new StringBuilder();
        StringBuilder s8 = new StringBuilder();
        //16 -> 2
        for(char c : str.toCharArray()){
            if(c == '0'){
                s2.append("0000");
            }else if(c == '1'){
                s2.append("0001");
            }else if(c == '2'){
                s2.append("0010");
            }else if(c == '3'){
                s2.append("0011");
            }else if(c == '4'){
                s2.append("0100");
            }else if(c == '5'){
                s2.append("0101");
            }else if(c == '6'){
                s2.append("0110");
            }else if(c == '7'){
                s2.append("0111");
            }else if(c == '8'){
                s2.append("1000");
            }else if(c == '9'){
                s2.append("1001");
            }else if(c == 'A'){
                s2.append("1010");
            }else if(c == 'B'){
                s2.append("1011");
            }else if(c == 'C'){
                s2.append("1100");
            }else if(c == 'D'){
                s2.append("1101");
            }else if(c == 'E'){
                s2.append("1110");
            }else if(c == 'F'){
                s2.append("1111");
            }
        }
        //2 -> 8

        //每三位 为8进制的一位
        if(s2.length() % 3 == 1){
            s2.insert(0, "00");
        }else if(s2.length() % 3 == 2){
            s2.insert(0, "0");
        }
        for(int i = 0; i < s2.length(); i += 3){
            String bit = s2.substring(i, i + 3);
            if(i == 0 && bit.equals("000")) s8.append("");
            else{
                int num = (bit.charAt(0) - '0') * 4 + (bit.charAt(1) - '0') * 2 + (bit.charAt(2) - '0');
                s8.append(num);
            }
        }
        return s8.toString();
    }
}